package com.lsa.edmonds.chap1;

import java.util.List;

import com.lsa.helpers.Utils;
import com.lsa.shenn.common.Sorter;

public class SelectionSort implements Sorter
{
	public int[] sort(int[] array) 
	{
		if (Utils.isEmpty(array))
			return array;
		
		int smallestElemIdx = 0;
		
		while(smallestElemIdx != array.length)
		{
			int min = Integer.MAX_VALUE;
			int minIdx = smallestElemIdx;
			
			for (int i = smallestElemIdx; i < array.length; i++)
			{			
				if (min > array[i])
				{
					min = array[i];
					minIdx = i;
				}
			}
			
			Utils.swap(array, smallestElemIdx, minIdx);
			
			//$LOOP_INVARIANT:
			// for_all(i <= smallestElemIdx) : array[..i] sorted
			
			smallestElemIdx++;
		}
		
		return array;
	}

	public List<Integer> sort(List<Integer> array)
	{
		return null;
	}
}
